| Dozent | Prof. Dr. Klaus-Jörn Lange |
| Sprechstunde | Do 13.30 14.30 und n.V. |
| Zeit | Di 1618, Do 1618 |
| Umfang | 4+2 |
| Ort | siehe Aushang |
| Turnus | jährlich |
| Prüfungsfach | Theoretische Informatik |
Beschreibung:
Die Komplexitätstheorie klassifiziert die berechenbaren Probleme
nach der Schwierigkeit ihrer Lösbarkeit durch Computer.
Ein besonderer Augenmerk liegt dabei in der Ermittlung von Gründen
für die hartnäckige Schwierigkeit einiger Probleme.
Dieses Gebiet ist erst vor ca. 25 Jahren ein Forschungsthema geworden,
hat sich aber inzwischen enorm ausgeweitet und umfaßt heute einen
großen Bereich der Forschungsaktivitäten
in der Theoretischen Informatik.
In der Vorlesung soll ausgehend von der Betrachtung konkreter
Probleme der theoretische Rahmen für das Verständnis
einiger komplexitätstheoretischer Kernresultate erarbeitet werden.
Die folgenden Stichworte deuten den etwaigen Aufbau der Vorlesung an:
sequentielle Berechnungsmodelle,
Komplexitätsklassen, Größ ter und durchschnittlicher
Betriebsmittelaufwand,
die Klassen P und NP,
Komplexität von Optimierungsproblemen,
das Primzahlproblem und die Klasse UP, die Polynomielle Hierarchie,
Platzkomplexitätsklassen, Probabilistische Komplexitätsklassen,
Interaktive Beweissysteme, Schaltkreise und
parallele Modelle.
Voraussetzungen:
Informatik III
Literatur:
Wird in der Vorlesung vorgestellt.